package week02

// 239. 滑动窗口最大值
// https://leetcode-cn.com/problems/sliding-window-maximum/

func maxSlidingWindow(nums []int, k int) []int {
	var ans []int
	heap := &BinaryHeap{}
	for i := 0; i < k-1; i++ {
		heap.push(newElem(i, nums[i]))
	}
	for i := k-1; i < len(nums); i++ {
		heap.push(newElem(i, nums[i]))
		for {
			elem := heap.top()
			if elem.idx >= i-k+1 {
				break
			}
			heap.pop()
		}
		ans = append(ans, heap.top().val)
	}
	return ans
}

func newElem(idx, val int) *Elem {
	return &Elem{
		val: val,
		idx: idx,
	}
}

type Elem struct {
	val int
	idx int
}

// 大顶堆
type BinaryHeap struct {
	list []*Elem
}

func (heap *BinaryHeap) push(elem *Elem) {
	heap.list = append(heap.list, elem)
	var cur = len(heap.list) - 1
	var parent = (cur - 1) / 2
	for parent >= 0 {
		if heap.list[cur].val > heap.list[parent].val {
			heap.list[cur], heap.list[parent] = heap.list[parent], heap.list[cur]
			cur = parent
			parent = (cur - 1) / 2
		} else {
			break
		}
	}
}

func (heap *BinaryHeap) pop() {
	heap.list[0] = heap.list[len(heap.list)-1]
	heap.list = heap.list[:len(heap.list)-1]
	var cur = 0
	var child = cur * 2 + 1
	for child < len(heap.list) {
		var other = cur * 2 + 2
		if other < len(heap.list) && heap.list[other].val > heap.list[child].val {
			child = other
		}
		if heap.list[cur].val < heap.list[child].val {
			heap.list[cur], heap.list[child] = heap.list[child], heap.list[cur]
			cur = child
			child = cur * 2 + 1
		} else {
			break
		}
	}
}

func (heap *BinaryHeap) top() *Elem {
	return heap.list[0]
}

func (heap *BinaryHeap) empty() bool {
	return len(heap.list) == 0
}